package acwing._1_1AlgorithmBasic._3SearchGraph;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic._3SearchGraph
 * @File : Q0850.java
 * @Author : WangRuoyu
 * @Date 2023/4/2 16:12
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Q0850 {
    static int n;
    static int m;
    static int[] h;
    static int[] w;
    static int[] e;
    static int[] next;
    static int idx = 0;

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        next[idx] = h[a];
        h[a] = idx++;
    }

    static int[] dijkstra2(int x) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        boolean[] st = new boolean[n + 1];
        int[] res = new int[n + 1];
        Arrays.fill(res, 0x3f3f3f3f);
        res[x] = 0;
        pq.add(new int[]{0, x});
        while (!pq.isEmpty()) {
            int[] point = pq.poll();
            int dis = point[0];
            int t = point[1];
            if (st[t]) continue;
            for (int i = h[t]; i != -1; i = next[i]) {
                int j = e[i];
                if (res[j] > dis + w[i]) {
                    res[j] = dis + w[i];
                    pq.add(new int[]{res[j], j});
                }
            }
            st[t] = true;
        }

        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);
        h = new int[n + 1];
        w = new int[m + 10];
        e = new int[m + 10];
        next = new int[m + 10];
        Arrays.fill(h, -1);

        for (int i = 0; i < m; i++) {
            words = br.readLine().split(" ");
            int a = Integer.parseInt(words[0]);
            int b = Integer.parseInt(words[1]);
            int c = Integer.parseInt(words[2]);
            add(a, b, c);
        }

        int[] res = dijkstra2(1);
        if (res[n] != 0x3f3f3f3f) {
            System.out.println(res[n]);
        } else {
            System.out.println(-1);
        }
    }
}
